﻿#include "Generation/Graph/AdGraph.h"

#include <functional>

AdGraph::AdGraph(int vCount)
{
	VertexCount = vCount;
	_vertexList.Init(nullptr, VertexCount);
}

void AdGraph::SetIndex(int index, FString value)
{
	if (_vertexList[index] == nullptr)
	{
		_vertexList[index] = new FVertexNode(value);
		_vertexList[index]->Index = index;
	}
	else
	{
		_vertexList[index]->VertexName = value;
		_vertexList[index]->Index = index;
	}
}

FString AdGraph::GetIndex(int index)
{
	return _vertexList[index] == nullptr
		       ? "NULL"
		       : _vertexList[index]->VertexName;
}

void AdGraph::AddEdge(int startVertexID, int endVertexID, int weight)
{
	int i = startVertexID;
	int j = endVertexID;

	FEdgeNode* temp = _vertexList[i]->FirstNode;
	if (temp == nullptr)
	{
		_vertexList[i]->FirstNode = new FEdgeNode(j, weight);
	}
	else
	{
		while (temp->Next != nullptr)
			temp = temp->Next;
		temp->Next = new FEdgeNode(j, weight);
	}
}

TArray<TreeEdge*> AdGraph::GetEdges()
{
	for (int i = 0; i < VertexCount; i++)
		_vertexList[i]->Visited = false;

	TArray<TreeEdge*> result;

	for (int i = 0; i < VertexCount; i++)
	{
		_vertexList[i]->Visited = true;
		FEdgeNode* p = _vertexList[i]->FirstNode;
		while (p != nullptr)
		{
			if (_vertexList[p->Index]->Visited == false)
			{
				TreeEdge* edge = new TreeEdge(i, p->Index, p->Weight);
				result.Add(edge);

				//Debug.LogError("边：" + edge.Begin + " " + edge.End + " " + edge.Weight);
			}
			p = p->Next;
		}
	}

	result.Sort([](const TreeEdge& object1, const TreeEdge& object2)
	{
		return object1.Weight < object2.Weight;
	});
	return result;
}

int AdGraph::Find(const TArray<int>& parent, int f)
{
	while (parent[f] > 0)
		f = parent[f];
	return f;
}

TArray<FSpanTreeNode*> AdGraph::MiniSpanTree()
{
	TArray<int> parent;
	for (int i = 0; i < VertexCount; i++)
	{
		parent.Emplace(0);
	}
	TArray<FSpanTreeNode*> tree;
	int count = 0;
	TArray<TreeEdge*> edges = GetEdges(); //获得图中所有单向边，按照距离排序
	
	FSpanTreeNode* root = nullptr; // 找到根节点
	for (int i = 0; i < edges.Num(); i++)
	{
		int _begin = edges[i]->Begin;
		int _end = edges[i]->End;
		int _n = Find(parent, _begin);
		int _m = Find(parent, _end);
		if (_n != _m)
		{
			if (i == 0)
			{
				auto treeNode = new FSpanTreeNode(_vertexList[_begin], nullptr, 0);
				tree.EmplaceAt(count, treeNode);
				root = treeNode;
				count++;
			}
			parent[_n] = _m;
			tree.EmplaceAt(count, new FSpanTreeNode(_vertexList[_end], _vertexList[_begin], edges[i]->Weight));
			count++;
		}
	}
	
	int curDepth = -1;
	std::function<void(TArray<FSpanTreeNode*>)> SetDepthRecursive;
	SetDepthRecursive = [&curDepth, tree, &SetDepthRecursive](TArray<FSpanTreeNode*> levelNodes)
	{
		curDepth++;
	
		for (auto item : levelNodes)
		{
			item->Depth = curDepth;
		}
	
		TArray<FSpanTreeNode*> nextLevelNodes;
		for (auto item : tree)
		{
			if (item->Depth == -1) //还没确定深度的节点，需要查看是否是当前谁的孩子，还需要查看它是否反了。
			{
				for (auto item2 : levelNodes)
				{
					if (item->ParentContext == item2->SelfContext)
					{
						//找到了，没反不需要翻转
						item->ParentNode = item2;
						item2->ChildrenNodes.Add(item);
						nextLevelNodes.Add(item);
						break;
					}
					else if (item->SelfContext == item2->SelfContext)
					{
						item->Flip(); //找到了，反了，翻转
						item->ParentNode = item2;
						item2->ChildrenNodes.Add(item);
						nextLevelNodes.Add(item);
						break;
					}
				}
			}
		}
	
		if (nextLevelNodes.Num() > 0)
		{
			SetDepthRecursive(nextLevelNodes);
		}
	};
	
	SetDepthRecursive(*new TArray<FSpanTreeNode*>{root});
	
	TArray<int> parentCount;
	parentCount.Init(0, tree.Num());
	for (int i = 0; i < tree.Num(); i++)
	{
		parentCount[tree[i]->SelfContext->Index]++;
	}
	
	tree.Sort([](const FSpanTreeNode& object1, const FSpanTreeNode& object2)
	{
		return object1.Depth < object2.Depth;
	});
	return tree;
}
